package com.haidechizi.leetcode;

import java.util.List;
import java.util.Stack;

/**
 * @author: wangdejun
 * @create: 2020-04-14 09:26
 **/
public class _445_两数相加2 {

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        int length1 = length(l1);
        int length2 = length(l2);
        ListNode head = null;

        ListNode big = null;
        ListNode small = null;
        int div = length1 - length2;
        if (div >= 0) {
            big = l1;
            small = l2;
        } else {
            big = l2;
            small = l1;
            div = -div;
        }

        Stack<ListNode> stack = new Stack<>();
        while (div > 0) {
            stack.push(big);
            big = big.next;
            div--;
        }
        while (big != null) {

            big.val = big.val + small.val;
            stack.push(big);
            big = big.next;
            small = small.next;
        }
        int pre = 0;
        while (!stack.isEmpty()) {
            ListNode node = stack.pop();
            node.val = node.val + pre;
            if (node.val / 10 == 1) {
                node.val = node.val % 10;
                pre = 1;
            } else {
                pre = 0;
            }
            if (stack.isEmpty()) {
                head = node;
            }
        }
        if (pre == 1) {
            ListNode node = new ListNode(1);
            node.next = head;
            head = node;
        }
        return head;
    }

    public int length(ListNode listNode) {
        int count = 0;
        while (listNode != null) {
            count++;
            listNode = listNode.next;
        }
        return count;
    }
}
